package org.laizili.solution.leetcode;

import java.util.*;

/**
 * <a href="https://leetcode-cn.com/problems/find-servers-that-handled-most-number-of-requests/">1606-找到处理请求最多的服务器</a>
 * <p>
 * tags: 模拟; 数据结构
 *     <ol>
 *         <li>优先队列</li>
 *         <li>有序集合</li>
 *     </ol>
 * </p>
 */
public class Problem1606 {
    private static class Solution {
        public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
            NavigableSet<Integer> available = new TreeSet<>();
            for (int i = 0; i < k; i++) {
                available.add(i);
            }
            Queue<int[]> busy = new PriorityQueue<>((l, r) -> l[1] - r[1]);
            int[] counter = new int[k];
            for (int i = 0; i < arrival.length; i++) {
                while (!busy.isEmpty() && busy.peek()[1] <= arrival[i]) available.add(busy.poll()[0]);
                if (!available.isEmpty()) {
                    Integer idx = available.ceiling(i % k);
                    if (idx == null) {
                        idx = available.pollFirst();
                    }
                    available.remove(idx);
                    busy.offer(new int[]{idx, arrival[i] + load[i]});
                    counter[idx]++;
                }
            }
            final int max = Arrays.stream(counter).max().getAsInt();
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < counter.length; i++) {
                if (counter[i] == max) {
                    res.add(i);
                }
            }
            return res;
        }
    }
}
